package 题目集.线段树or树状数组.线段树;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.cn/problems/falling-squares/description/
 * 离散化+区间重置，区间最大值
 * 每次插入一个方块，先查询方块所在区域的最大值，
 * 然后将方块所在区域值重置为：原最大值+当前方块长度
 */
public class ch05_掉落的方块 {
    static Node[] tree;

    public List<Integer> fallingSquares(int[][] positions) {
        positions = agge(positions);
        int n = positions.length * 2;
        int tn = (int) Math.pow(2, Math.ceil(Math.log(n) / Math.log(2)) + 1);
        tree = new Node[tn];
        build(1, 1, n);
        List<Integer> list = new ArrayList<>(positions.length);
        for (int[] pos : positions) {
            long maxH = query(1, pos[0], pos[1]) + pos[2];    //之前的最大高度+现在高度，
            update(1, pos[0], pos[1], maxH);
            list.add((int) tree[1].val);
        }
        return list;
    }

    public static void build(int i, int l, int r) {
        tree[i] = new Node(l, r);
        if (l == r) return;
        int m = l + r >> 1;
        build(i << 1, l, m);
        build(i << 1 | 1, m + 1, r);
    }

    public static void update(int i, int l, int r, long v) {
        if (isLazy(i, l, r)) {
            updateLazy(i, v);
            return;
        }
        push(i);
        int m = tm(i);
        if (l <= m) update(i << 1, l, r, v);
        if (m < r) update(i << 1 | 1, l, r, v);
        pull(i);
    }

    public static long query(int i, int l, int r) {
        if (isLazy(i, l, r)) return tree[i].val;
        push(i);
        long res = 0;
        int m = tm(i);
        if (l <= m) res = query(i << 1, l, r);
        if (m < r) res = Math.max(res, query(i << 1 | 1, l, r));
        return res;
    }

    public static void push(int i) {
        if (tree[i].update != 0) {
            updateLazy(i << 1, tree[i].update);
            updateLazy(i << 1 | 1, tree[i].update);
            tree[i].update = 0;
        }
    }

    public static void pull(int i) {
        tree[i].val = Math.max(tree[i << 1].val, tree[i << 1 | 1].val);
    }

    public static void updateLazy(int i, long v) {
        tree[i].val = v;
        tree[i].update = v;
    }

    public static int tm(int i) {
        return tree[i].l + tree[i].r >> 1;
    }

    public static boolean isLazy(int i, int l, int r) {
        return l <= tree[i].l && tree[i].r <= r;
    }


    public static int[][] agge(int[][] arr) {
        int[] sort = new int[arr.length * 2];
        int[][] res = new int[arr.length][3];   //0:L,1:r,2:v
        for (int i = 0, j = 0; i < arr.length; i++) {
            sort[j++] = arr[i][0];
            sort[j++] = arr[i][0] + arr[i][1];
        }
        Arrays.sort(sort);
        for (int i = 0; i < arr.length; i++) {
            res[i][0] = rank(sort, arr[i][0]);
            res[i][1] = rank(sort, arr[i][0] + arr[i][1]) - 1;  //左闭右开变为左闭右闭，右端点-1
            res[i][2] = arr[i][1];
        }
        return res;
    }

    public static int rank(int[] sort, int v) {
        int l = 0, r = sort.length - 1;
        while (l <= r) {
            int m = l + r >> 1;
            if (sort[m] < v) {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if (l < sort.length && sort[l] <= v) {
            return l + 1;
        }
        return r + 1;
    }

    static class Node {
        int l, r;
        long val, update;
        //不会重置为0，所以不需要tag标记

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

    @Test
    public void test() {
        int[][] positions = {{9, 7}, {1, 9}, {3, 1}};
        List<Integer> list = fallingSquares(positions);
        System.out.println(list);
    }
}
